package leetCode.solution;

public class Solution1000 {
	public int mergeStones(int[] stones, int k) {
		int n = stones.length;
		if((n-1)%(k-1)!=0) return -1;
		int[] preSum = new int[n+1];
		preSum[0]=0;
		for(int i = 0;i<n;i++) {
			preSum[i+1] = preSum[i] + stones[i];
		}
		int [][][] dp = new int[n][n][k+1];
		return process(0, n-1, 1, stones, k, preSum, dp);
	}
	
	private int process(int l, int r, int rest, int[] stones, int k, int [] preSum, int [][][] dp) {
		if(dp[l][r][rest]!=0) {
			return dp[l][r][rest];
		}
		if(l==r) {
			dp[l][r][rest] = rest==1?0:-1;
			return rest==1?0:-1;
		}
		if(rest==1) {
			int last = process(l, r, k, stones, k, preSum, dp);
			if(last==-1) {
				dp[l][r][rest] = -1;
				return -1;
			}
			dp[l][r][rest] = last + preSum[r+1]-preSum[l];
			return last + preSum[r+1]-preSum[l];
		}else {
			int ans = Integer.MAX_VALUE;
			for(int mid=l;mid<r;mid+=k-1) {
				int last1 = process(l, mid, 1, stones, k, preSum, dp);
				int last2 = process(mid+1, r, rest-1, stones, k, preSum, dp);
				if(last1!=-1 && last2!=-1) {
					ans = Math.min(ans, last1+last2);
				}
			}
			dp[l][r][rest] = ans; 
			return ans;
		}
	}
}
